import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
 * User: wangxin
 * Date: 2025-04-08
 * Time: 21:29
 */
public class Test3 {
    public int triangleNumber(int[] nums) {
        if(nums == null||nums.length < 3){
            return 0;
        }
        int n = nums.length;
        Arrays.sort(nums);
        int ans = 0;
        for(int i = 0;i < n;i++){
            for(int j = i+1;j < n;j++){
                int left = j+1,right = n - 1,k = j;
                while(left <= right){
                    int mid = (left+right)/2;
                    if(nums[mid] < nums[i]+nums[j]){
                        k = mid;
                        left = mid+1;
                    }else{
                        right = mid - 1;
                    }
                }
                ans += k-j;
            }
        }
        return ans;
    }
}
